#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef enum { false, true } bool;
#define kInfinity (1e9)
typedef int ElemSet; /* 默认矩阵元素为整型 */
typedef struct MatrixNode *Matrix;
struct MatrixNode {
    ElemSet **m;
    int row;
    int col;
};

ElemSet **Create2DArray(int row, int col) {
    /* 动态声明row行col列的二维数组 */
    ElemSet *a, **t;
    int i;

    a = (ElemSet *)malloc(sizeof(ElemSet) * row * col);
    t = (ElemSet **)malloc(sizeof(ElemSet *) * row);
    for (i = 0; i < row; i++)
        t[i] = &a[col * i];
    return t;
}

void Free2DArray(ElemSet **t) {
    /* 释放二维数组空间 */
    free(t[0]);
    free(t);
}

void PrintOrder(Matrix p, int i, int j) {
    /* 递归输出乘法顺序 */
    int k;

    if (i < j) {
        k = p->m[i][j]; /* 最优划分为(M[i,k])x(M[k+1,j]) */
        printf("(");
        PrintOrder(p, i, k); /* 输出M[i,k] */
        printf(")x(");
        PrintOrder(p, k + 1, j); /* 输出M[k+1,j] */
        printf(")");
    } else { /* 只有一个矩阵，直接输出 */
        printf("M%d", i + 1); /* 注意：矩阵编号从 1 开始 */
    }
}

/* 算法15-10 计算m_(1,n)的动态规划算法 OptimalMatrixOrdering (m, p, r, n) */
void OptimalMatrixOrdering(Matrix m, Matrix p, int *r, int n) {
    int i, j, k, length;
    int this_m;

    for (i = 0; i < n; i++) {
        m->m[i][i] =
            0; /* 最小规模问题的解：只有1个矩阵，不需要计算 */
    }
    for (length = 1; length < n;
            length++) { /* length=j-i,即 M[i,j] 中矩阵相乘的次数 */
        for (i = 0; i < (n - length); i++) {
            j = i + length; /* 在固定长度下从左到右顺序考察所有 M[i,j 序列 */
            m->m[i][j] = kInfinity; /* 将 m[i][j] 初始化 */
            for (k = i; k < j;
                    k++) { /* 对应每个k划分，根据公式计算当前最优 */
                this_m = m->m[i][k] + m->m[k + 1][j] + r[i] * r[k + 1] * r[j + 1];
                if (this_m < m->m[i][j]) { /* 若当前值更优 */
                    m->m[i][j] = this_m; /* 则更新最优解 */
                    p->m[i][j] = k; /* 且记录划分位置 */
                }
            }
        }
    }
}
/* 算法15-10 结束 */

int main(void) {
    Matrix m, p;
    int *r;
    int n, i;

    scanf("%d", &n);
    m = (Matrix)malloc(sizeof(struct MatrixNode));
    m->row = n;
    m->col = n;
    m->m = Create2DArray(m->row, m->col);
    p = (Matrix)malloc(sizeof(struct MatrixNode));
    p->row = n;
    p->col = n;
    p->m = Create2DArray(p->row, p->col);
    r = (int *)malloc(sizeof(int) * (n + 1));
    for (i = 0; i <= n; i++) {
        scanf("%d", &r[i]);
    }
    OptimalMatrixOrdering(m, p, r, n);
    PrintOrder(p, 0, n - 1);
    printf("\n%d\n", m->m[0][n - 1]);
    Free2DArray(m->m);
    free(m);
    Free2DArray(p->m);
    free(p);

    return 0;
}